#include <stdio.h>
#include <stdlib.h>

//平衡二叉树
/*
结点的平衡因子=左子树高-右子树高
*/

typedef struct AVLNode
{
    int key;
    int balance; //平衡因子
    struct AVLNode *lchild, *rchild;
} AVLNode, *AVLTree;

/*
二叉排序树插入结点保持平衡
从插入结点往回找第一个不平衡结点，调整以该结点为根的子树（最小不平衡子树）

调节最小不平衡子树A
LL  在A的左孩子的左子树插入导致不平衡
将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树成为A结点的左子树

RR  在A的右孩子的右子树插入导致不平衡
将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树成为A结点的右子树


LR  在A的左孩子的右子树插入导致不平衡
先左旋转后右旋转先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后再把该C结点向右上旋转提升到A结点的位置 （相当于对B  RR）
将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树成为A结点的左子树   （相当于对A  LL）


RL  在A的右孩子的左子树插入导致不平衡
先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置，然后再把该C结点向左上旋转提升到A结点的位置  相当于对B（LL）
再将A   RR



*/


int main()
{
    printf("\n\n========================================================================\n\n");

    printf("\n\n========================================================================\n\n");
    return 0;
}